package leetcode_top;

import java.util.*;

import org.junit.Test;

import utils.BracketUtils;


public class Ex454 {
    class Solution1 {
        int[][] nums;
        int n;
        Map<String, Integer> map;
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
            nums = new int[4][];
            nums[0] = nums1;
            nums[1] = nums2;
            nums[2] = nums3;
            nums[3] = nums4;
            res = new ArrayList<>();
            n = nums1.length;
            map = new HashMap<>();
            dfs(0, 0, new ArrayList<>());
            return res.size();
        }
        List<List<Integer>> res;
        public void dfs(int idx, int cur, List<Integer> list) {
            String s = idx + "_" + cur;
            if (map.containsKey(s)) {
                System.out.println("命中缓存");
                return;
            }
            if (idx == 4) {
                if (cur == 0) {
                    res.add(new ArrayList<>(list));
                }
                return;
            }

            for (int i = 0; i < n; i++) {
                list.add(nums[idx][i]);
                dfs(idx + 1, cur + nums[idx][i], list);
                list.remove(list.size() - 1);
            }
            map.put(s, 1);
        } 
    }

    @Test
    public void test() {
        Solution1 s = new Solution1();
        int[] nums1 = {1, 2},
        nums2 = {-2,-1},
        nums3 = {-1,2},
        nums4 = {0,2};
        System.out.println(s.fourSumCount(nums1, nums2, nums3, nums4));
    }

    /* 
        很巧妙的思路：
        借助两数之和的思想，可以用map存储一个元素，而去找另一个元素的相反数

        若map存储一个数组之和，遍历剩下三个数组就是O(N^3)
        若map存储三个数组之和，遍历这三个数组存入map就是O(N^3)
        若map存储两个数组之和，遍历这两个数组存入map就是O(N^2)，遍历剩下两个数组就是O(N^2)

        因此选择第三种，时间复杂度O(N^2)
    */
    class Solution {
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
            Map<Integer, Integer> map = new HashMap<>();
            int len = nums1.length, sum;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    sum = nums1[i] +nums2[j];
                    map.put(sum, map.getOrDefault(sum, 0) + 1);
                }
            }
            int res = 0, t;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    sum = nums3[i] +nums4[j];
                    if (map.containsKey(-sum)) {
                        t = map.get(-sum);
                        res += t;
                    }
                }
            }

            return res;
        }
    }

    @Test
    public void test2() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[-1,-1],[-1,1],[-1,1],[1,-1]]");
        System.out.println(s.fourSumCount(nums[0], nums[1], nums[2], nums[3]));
    }
}
